Bar code has become broadly accepted as the primary means for automatically identifying and tracking objects ranging in size from large freight containers down to printed circuit boards and other moderately small components. A bar code is typically a linear array of elements that are either printed directly on the object to be identified and/or tracked, or printed on labels that are attached to the object. The bar code elements are bars and spaces. The bars represent strings of binary ones, and the spaces represent strings of binary zeros. They are generally read by optical techniques, such as scanning laser beams or handheld wands. One common example of a bar code is the Universal Product Code (UPC).
The contrasting parallel bars and spaces of a bar code have varying widths. Generally, the bars and spaces can be no smaller than a specified minimum width, termed the code's "unit" (or "x-dimension" or "module"). While the theoretical minimum unit size is the wavelength of the light being used to read the bar code, there are other practiaal limitations. Among them are the desired depth of field of the reading equipment, the limitations of a given printing process, and the robustness of the printed image to be correctly read despite dust, dirt, and minor physical damage.
A common example of a bar code structure is CODE 39, which enjoys broad acceptance in manufacturing, hospitals, libraries, universities, and government agencies. It is used for alphanumeric labeling applications. CODE 39 (also known as "3 of 9 Code") is so named because the original concept provided for 39 characters. The name also derives from its 3 out of 9 structure wherein 3 of 9 elements (i.e., bars or spaces) are wide and the remaining 6 are narrow.
The complete forty-four character set of CODE 39 includes a Start/Stop character and forty-three data characters. The data characters consist of the ten digits, the twenty-six letters of the alphabet, the space, and the six symbols, "-", ".", "$", "/", "+", and "%". It is possible to represent a character which is not in the basic set of forty-three data characters (such as an ASCII character) in CODE 39. Any of the 128 ASCII characters is represented by using the characters $, /, +, and % as precedence characters in front of one of the alphabetic characters. For example, "+B" represents a lower case letter b while "$B" represents a "control" B (the ASCII "STX" character).
Most of the characters in CODE 39 are represented by a stand-alone group of five bars with their four included spaces. Two of the five bars are wide, giving (5!/2!3!)=10 possible bar configurations, and one of the four spaces is wide, giving 4.times.10=40 possible characters. The four additional characters ($, /, +, and %) are structured with all the bars narrow and three spaces wide.
CODE 39 is self-checking. This strong property, along with its variable length and capability of handling alphanumeric data, means that it can be successfully printed by a very broad variety of equipment and processes.
One problem with CODE 39 is that each of its characters is relatively wide, occupying thirteen to sixteen units of width. This can be important where constraints due to printing equipment (such as matrix line printers) impose a minimum size on individual bar widths. Another bar code, CODE 93, is a very high density alphanumeric symbology designed explicitly as a companion to CODE 39 and intended to overcome this problem. The set of data characters in CODE 93 is identical to that of CODE 9. Self-discriminating bar code readers or scanners can read either CODE 39 or CODE 93 without operator intervention. This compatibility allows CODE 93 symbols to be introduced into existing systems with minimal impact.
CODE 93 is a (9,3) code of the (n,k) family defined by Savir and Laurer in "The Characteristics and Decodability of the Universal Product Code," IBM Systems Journal, Vol. 14, No. 1, 1975. (n,k) codes represent characters uniquely by a string of n bits containing k runs of 1 bits (i.e., k bars) and k runs of zero bits (i.e., k spaces). The first bit of a character has a binary value of one. An (n,k) code is decodable backwards. The name, CODE 93, derives from this (n,k) notation.
Each CODE 93 character consists of 9 units arranged into three bars and three spaces. Forty-eight of the fifty-six possible combinations are used in CODE 93. One of these characters is reserved for a start/stop character, four are used for control characters, and the forty-three remaining data characters are identical to those in CODE 39. CODE 93 uses two check characters. A termination bar is added after the stop character to close off the final space.
CODE 93 is continuous and non-self-checking. Bar and space width may be 1, 2, 3, or 4 units wide. Its structure facilitates using the edge-to-edge decoding of the UPC described by Savir and Laurer. The resulting symbol is inherently immune to uniform ink spread, which allows liberal bar width tolerances.
Today's open standards for bar code specify a minimum nominal unit of 0.0075 inch. The bar height is typically recommended to be 15 percent or more of the overall symbol length, excluding quiet zones which do not contain coded information.
To measure how efficiently codes represent data, it is necessary to develop a simple measure of efficiency. Whereas in one-dimensional structures, such as bar codes, the accepted measure of space consumption is the unit, for two dimensions, an appropriate measure is the square unit.
Information content is measured in bits. For a character-based system, it is assumed that all characters in the set are equally probable, so that if C is the size of the character set, then the information content, I, in bits per character, is I=log.sub.2 C. For example, if only the ten digits are represented, then C equals 10, and I equals 3.322 bits per character. If, instead, the full ASCII set of 128 characters is to be represented, then C equals 128, and I equals 7. CODE 39, having 43 data characters, contains 5.426 bits per character, excluding the overhead of the code's start and stop characters and any check or flag characters in the application data stream.
For bar code, efficiency is measured in bits per unit, while for two-dimensional systems, efficiency is measured in bits per square unit. Gross efficiency excludes all of the overhead characters, while net efficiency considers a whole symbol, including start, stop, and check characters. A 100 percent efficient system would provide one bit of information per unit if it were one-dimensional, or one bit per square unit if it were two-dimensional. Since all practical systems must provide for orientation, clocking, and checking, their net efficiencies will always be less than 100 percent. In the case of a synchronous ASCII data transmission (where unit time intervals are equivalent to the unit dimension of a bar code), overhead typically includes a start bit, a stop bit, and a parity bit, so that ten units are required to convey seven information bits. A synchronous ASCII transmission therefore has a gross efficiency of 70 percent.
The following table indicates the gross and net efficiencies of CODE 39 and CODE 93:
TABLE 1 ______________________________________ Gross efficiency Net efficiency (bits per unit) (bits per unit) ______________________________________ CODE 39 37.4% 34.0% (19 characters) CODE 93 61.7% 50.2% (18 characters) ______________________________________
Considering an 18 character string of CODE 93 characters (containing 18.times.log.sub.2 47=99.983 bits), its two-dimensional efficiency as a function of varying symbol height is shown in the following table:
TABLE 2 ______________________________________ Symbol Height, Efficiency, Bits Units per Square Unit ______________________________________ 30 0.017 20 0.025 4 0.126 2 0.251 1 0.502 ______________________________________
The efficiency of a 5.times.7 dot matrix array displaying the 128 ASCII characters is 7/48=0.146 bits per square unit, assuming that each character is bordered by a unit, assuming that each character is bordered by a unit of space to its right and another unit of space below. Therefore, a four unit high string of eighteen CODE 93 characters has essentially the same area efficiency as a string of 5.times.7 dot matrix characters. However, with a unit size of 0.0075 inch, the string of eighteen CODE 93 characters is about one and one-half inches long. Even if the unit size is reduced to 0.003 inch, the symbol length is still 0.6 inch, which is too long for labeling very small objects. Thus, the problem with bar code is not so much one of area efficiency as one of excessive symbol length.
It can be desirable to attach bar code symbols to very small objects, such as surface mount electronic devices. Such small components, having areas on the order of one-quarter inch on a side cannot be labeled with currently available linear arrays of bar code symbols.
Potential solutions to the problem of the need for a miniature printed code include (1) an optical character recognition (OCR) system, (2) a unique, two-dimensional optical marking system, (3) a tiered bar code, and (4) a new symbology structure compatible with prevailing standard bar codes. OCR presents problems of reading complexity and only moderate spatial efficiency. Data accuracy is achievable by adding a sufficient number of redundant check characters, but this exacerbates the space efficiency problem.
Unique, two-dimensional optical marking systems most space-efficient alternative. Two-dimensional structures are analyzed as a whole, i.e., they are not analyzed as a series of one-dimensional structures. Accordingly, their analysis is more complex and the equipment to perform the analysis is more expensive. Various two-dimensional structures have been proposed, and some have been implemented. TEMA Code, devised by Ray Stevens in the late 1970s, is a two-dimensional extrapolation of CODE 39. It was originally intended to be read by a hand-held device similar to the charge-coupled device (CCD) readers used to scan OCR characters. More recently, VERICODE (a trademark of VERITEC Corporation) has been promoted for labeling of small objects. Essentially, VERICODE (tm) is a checkerboard-like pattern of black or white square units. Published literature from VERITEC suggests two-dimensional space efficiencies in the range of 65 percent and better. VERICODE (tm) is not presently an open system. It appears to require vision system techniques for scanning.
The problem of restricted length on miniature objects might be solved by using a tiered bar code. For example, the AIAG shipping label consists of four or more bar code symbols arranged in four rows. By using multiple symbols in rows, the overall length can be significantly reduced. For example, eight tiers of CODE 93, each row containing four data digits, has a total capacity of thirty-two alphanumeric characters.
It is quite easy to scan such a symbol with a hand-held moving beam laser scanner or with a rastering-type scanner. However, it is not particularly easy to select the individual rows in precise sequence. If the reading order of the rows doesn't matter, this difficulty is unimportant. However, if the reading order is important, some means for making the rows self-identifying must be established. This could be accomplished by making the first character of each row a row identifier. This, however, would reduce the data capacity of the CODE 93 example to three characters per row (twenty-four characters in eight rows), significantly reducing the efficiency of such a code.
If a scanner were specially programmed to read multiple rows of CODE 93, sort them into row sequence, and strip out the row identifiers before transmitting the message, then the structure would become practical. However, the high overhead in CODE 93 and the lack of a natural means of identifying rows makes this proposal less than optimum. Any of the standard bar codes could be thus arranged in a tiered structure, but the built-in overhead makes these structures space inefficient.
In accordance with the foregoing analysis, it is known that a predetermined length of bar code symbols can represent a larger number of purely numerical data characters than alphanumeric characters (even if they are all numbers). This is so because each character taken from a purely numeric collection of characters contains less information than does each numeric character taken from an alphanumeric collection of characters.
It is therefore desirable to have a new symbology specifically designed for miniature object identification and tracking. It is also desirable to be able to have such a new symbology that can more efficiently represent strings of purely numeric data than is possible with alphanumeric representations.